#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;

vector<int> findSubstring(string s, vector<string>& words) {
    //words计算words中的种类和个数
    unordered_map<string, int> hash_word;
    for (auto e : words)
    {
        hash_word[e]++;
    }

    //注意一共需要三次滑动窗口，每次起始点加一
    int left = 0;
    int right = 0;
    int len = words[0].size();//words字符串的长度
    vector<int> index;//有效子串位置
    for (int i = 0; i < len; i++)
    {
        left = i;//【注意】内层滑动窗口也是改变了left的，所以每次出循环left也要重新赋值
        right = left;
        unordered_map<string, int> hash;
        //标记有效的count
        int count = 0;
        for (; right + len <= s.size(); right += len)//单次滑动窗口
        {

            string str(s.begin() + right, s.begin() + right + len);
             if (++hash[str] <= hash_word[str])//先进窗口，再判断是否有效，【注意】这里的str如果在hash_word中没有的话，就需要重新创建这个元素放到哈希表里，所以可以通过hash_word.count(find)判断优化
          
            {
                count++;
            }
            if (count == words.size() && (right - left+len) / len == words.size())//有效字符串个数和滑动区间长度都要满足【注意】这里计算滑动窗口内元素个数方法
            {
                //可以记录
                index.push_back(left);
                    //出窗口
                    string strl(s.begin() + left, s.begin() + left + len);
                    hash[strl]--;
                    left += len;
                    count--;
            }

            if((right - left+len) / len >= words.size())//滑动区间大于等于有效字符串个数
            {
                string str2(s.begin() + left, s.begin() + left + len);
                 if (hash_word.count(str2)&&hash[str2] <= hash_word[str2])
                {
                    count--;
                }
                hash[str2]--;
                left += len;
            }
          

        }
    }
    return index;
}


int main()
{

    vector<int> nums = { 5,2,3,1,1 };
    vector<int> nums1 = { 1,1 };
    vector<int> nums2 = { 5,6,7,8,9 };
    vector<int> nums3 = { 8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,1231,6309 };
    vector<string>vs = { "fooo","barr","wing","ding","wing" };
    string s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
    findSubstring(s, vs);

}